/**
 * https://leetcode-cn.com/problems/next-permutation/
 * 下一个排列
 * @param nums 
 */
const nextPermutation = (nums: number[]): void => {
    // 123456 -> 123465 -> 123546(123564 5和4交换之后, 让5后面的数进行翻转从而得到最小的值)

    const len = nums.length;
    // 边界判断
    if (len <= 1) return;
    let i = len - 2;

    /**
     * 交换i和j位置的元素
     * @param i 
     * @param j 
     */
    const swap = (i: number, j: number) => {
        const tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
    }

    /**
     * 翻转[s, e]的数组
     */
    const reverse = (s: number = 0, e: number) => {
        while (s < e) {
            swap(s, e)
            s++;
            e--
        }
    } 


    // 从后往前找到nums[i] < nums[i + 1] 的位置i
    while ( i >= 0 && nums[i] >= nums[i + 1]) {
        // 直到找到 nums[i] < nums[i + 1]
        i--
    }
    if (i < 0) {
        // 说明序列是从大到小排序的, 直接进行翻转转
        reverse(0, len - 1)
    } else {
        // 从后往前[i + 1, len - 1]找到第一个比i大的位置j, 进行然后和i位置进行交换
        let j = len - 1;
        // 直到找到nums[j] 大于了nums[i]
        while (nums[j] <= nums[i]) {
            j--
        }

        // 交换 i 和 j的位置
        swap(i, j)

        // 翻转[i + 1, len - 1] 的元素
        reverse(i + 1, len - 1)
    }
    
    
};

const arrs = [1, 1, 1, 1]
nextPermutation(arrs)

console.log(arrs)